package com.swust.dumpling.commons.utils;

/**
 * @author swust-cs-Dong6 B425
 * 自定义数学包
 * */
public class MathUtil {
	
	/**
	 * 判断是不是素数
	 *
	 * Judge if the input is not a prime number
	 * */

	public static boolean isPrime(int num) {
		if (num <=1)
			return false;
		if (num ==2)
			return true;
		
		int cou = ( (int) Math.sqrt(num)) + 1;
		
		for (int i = 2 ; i < cou ; i ++)
			if (num % i == 0)
				return false;
		return true;
	}
	
	
	/**
	 * 
	 * @param tt int the number before mod
	 * 
	 * 求乘法逆元用
	 * 
	 * element with multiplicative inverse
	 * */
	public static int getModLower(int tt , int bi) {
		int x1 , x2 , x3 , y1 , y2 , y3 , t1 , t2 , t3 , k;
		x1 = 1;
		x2 = 0;
		x3 = bi;
		y1 = 0;
		y2 = 1;
		y3 = tt;
		if(bi < tt) {
			k = bi ;
			bi = tt;
			tt = k;
		}
		while (true) {
			if (y3 == 0)
				return 0;
			if(y3 == 1)
				return y2<=0?y2+bi:y2;
			k = x3/y3;
			t1 = x1 - k * y1;
			t2 = x2 - k * y2;
			t3 = x3 - k * y3;

			x1 = y1;
			x2 = y2;
			x3 = y3;

			y1 = t1;
			y2 = t2;
			y3 = t3;
		}
	}
	
	/**
	 * 辗转相除判断互素 , 最大公约数
	 * Divide judge removed coprime
	 * @return a number == 1 : coprime
	 * */
	public static int coprime(int a , int b) {
		
		int tmp = 0;
		//ensure a is the max
		if (a <= b) {
			tmp = a;
			a = b;
			b = tmp;
		}
		tmp = a % b;
		if (tmp == 0)
			return b;
		else 
			return coprime(b, tmp);
	}

}
